iT邦幫忙

2024 iThome 鐵人賽

DAY 12
0
佛心分享-刷題不只是刷題

轉生理工組後從零開始的leetcode刷題系列 第 12

day-12[medium.2007]find original array from doubled array

  • 分享至 

  • xImage
  •  

An integer array original is transformed into a doubled array changed by appending twice the value of every element in original, and then randomly shuffling the resulting array.

Given an array changed, return original if changed is a doubled array. If changed is not a doubled array, return an empty array. The elements in original may be returned in any order.


題目說,有一組數組original
依照步驟
1.將original中的每個數字的兩倍附加到自身後面
2.整組打亂後獲得新數組changed
我們的目標就是把changed通過上述規則還原成original,無法還原就返回空數組

我的解題思路:
先思考changed應該要有的幾項特點

  • 數組長度一定是偶數
  • 每個元素都會配對成 x和2x 的組合

所以具體的解題方法應該是:
1.檢查數組長度,若為奇數直接返回空數組
2.把出現的數字做成一個陣列
3.針對每個數字n,做乘2的動作得到2n
4.如過2n存在陣列裡面,同時刪除這兩個數字並把n存到original
5.如過2n不存在陣列裡,則把n除以2得到n/2,
6.如過n/2存在陣列裡面,同時刪除這兩個數字並把n/2存到original
7.如過n/2依然不存在陣列裡,則返回空數組
8.成功遍歷完所有陣列的數後,返回original


class Solution {
    public int[] findOriginalArray(int[] changed) {
        // 檢查數組長度
        if (changed.length % 2 != 0) {
            return new int[0];
        }
        // 把數字放進陣列
        List<Integer> numsList = new ArrayList<>();
        for (int num : changed) {
            numsList.add(num);
        }
        List<Integer> original = new ArrayList<>();
        // 開始遍歷配對
        while (!numsList.isEmpty()) {
            int n = numsList.remove(0);
            // 2*n
            Integer doublee = n* 2;
            if (numsList.contains(doublee)) {
                numsList.remove(doublee);
                original.add(n);
            } else {
                // 找不到就嘗試n/2
                if (n % 2 == 0) {
                    Integer half = n / 2;
                    if (numsList.contains(half)) {
                        numsList.remove(half);
                        original.add(half);
                    } else {
                        // 還是找不到
                        return new int[0];
                    }
                } else {
                    // n是奇數
                    return new int[0];
                }
            }
        }
        int[] result = new int[original.size()];
        for (int i = 0; i < original.size(); i++) {
            result[i] = original.get(i);
        }
        return result;
    }

我最近開始感覺到一點刷題的樂趣了!
可能是因為難度適中,挫折感和成就感取得了平衡吧?
總之經果一些小地方修改後,今天也挑戰成功~~
https://ithelp.ithome.com.tw/upload/images/20240927/20169432T6gVV1DGZs.png


上一篇
day-11[medium.2017]grid game
下一篇
day-13[medium.2063]vowels all substrings
系列文
轉生理工組後從零開始的leetcode刷題30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言